12318. Сумма в поле

Для заданных целых чисел a, b, c, n, p вычислите значение суммы:

Результат выведите в виде двух чисел x и y таких что

Вход. Пять целых чисел a, b, c, n, p. Известно, что:

· p < 10⁹ – простое число,

· 0 ≤ a, b < p,

· 1 ≤ c < p,

· 0 ≤ n ≤ 10⁹

Выход. Выведите два целых числа x и y – коэффициенты при 1 и соответственно, по модулю p.

Пример входа 1	Пример выхода 1
2 1 5 2 17	12 5
Пример входа 2	Пример выхода 2
3 2 5 10 17	15 6

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Вычисления следует выполнять в расширенном поле:

Правила операций:

· Сложение

· Умножение

Пусть x = . Тогда искомая сумма является конечной геометрической прогрессией:

1 + x + x² + x³ + … + xⁿ = =

Остается реализовать деление a = xⁿ⁺¹ – 1 на b = x – 1 в поле :

= = = =

Пример

В первом примере

=

(1 + () + ()) mod 17 = 12

Вычислим этот пример по формуле:

= =

= = = =

= = = =

= =

Во втором примере

= 15

Реализация алгоритма

Функция modpow вычисляет значение a^k mod p.

long long modpow(long long a, long long k, long long p)

{

long long res = 1;

a %= p;

while (k)

{

if (k & 1) res = res * a % p;

a = a * a % p;

k >>= 1;

}

return res;

}

Объявим структуру Num для хранения числа вида .

struct Num

{

long long x, y; // x + y*sqrt(c)

};

Реализуем сложение в поле . Функция add возвращает сумму чисел a и b.

Num add(Num& a, Num& b)

{

Num res;

res.x = (a.x + b.x) % p;

res.y = (a.y + b.y) % p;

return res;

}

Реализуем вычитание в поле . Функция sub возвращает разность чисел a и b.

Num sub(Num& a, Num& b)

{

Num res;

res.x = (a.x - b.x + p) % p;

res.y = (a.y - b.y + p) % p;

return res;

}

Реализуем умножение в поле . Функция mult возвращает произведение чисел a и b.

Num mult(Num& a, Num& b)

{

Num res;

res.x = (a.x * b.x + c * a.y % p * b.y) % p;

res.y = (a.x * b.y + a.y * b.x) % p;

return res;

}

Функция pow реализует возведение в степень baseⁿ, где base – число в поле .

Num pow(Num base, long long n)

{

Num res = { 1, 0 }; // единица поля

while (n > 0)

{

if (n & 1)

res = mult(res, base);

base = mult(base, base);

n >>= 1;

}

return res;

}

Функция divide реализует деление в поле . Она возвращает частное чисел a и b. Деление реализуем через умножение на сопряженное:

= = = =

Num divide(Num& a, Num& b)

{

Пусть conj = .

Num conj = { b.x, (p - b.y) % p };

Вычисляем n = .

Num n = mult(a, conj);

Вычисляем denom = .

long long denom =

((b.x * b.x) % p - ((b.y * b.y) % p * c) % p + p) % p;

Вычисляем обратный элемент и возвращаем n / denom = n * denom^-1.

long long inv_denom = modpow(denom, p - 2, p); // обратный элемент

return Num((n.x * inv_denom) % p, (n.y * inv_denom) % p);

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n, &p);

Инициализируем число x = и единицу поля one = .

Num x = { a % p, b % p };

Num one = { 1, 0 };

Вычисляем num = xⁿ⁺¹ – 1, denom = x – 1.

Num num = pow(x, n + 1);

num = sub(num, one);

Num denom = sub(x, one);

Вычисляем и выводим ответ res = num / denom = .

Num res = divide(num, denom);

printf("%lld %lld\n", res.x, res.y);